In order to compress and extend acoustic and visual digital data, various encoders and decoders are devised and practically used. An example of a standard compression scheme of acoustic data includes a Moving Picture Experts Group Audio Layer-3 (MP3), and an example of a standard compression scheme of visual data includes Joint Photographic Experts Group (JPEG).
In addition, Huffman encoding is a representative encoding method. In the Huffman encoding, for example, an appearance probability of each quantization value of an encoding target is learned, and a code book which is prepared by allocating a variable length code having a code length according to the appearance probability with respect to each of the quantization values in which the appearance probability is not 0 is used to perform the encoding.
At this time, a variable length code which is shorter in code length as the appearance probability of the quantization value increases is allocated, and a variable length code which is longer in code length as the appearance probability of the quantization value decreases is allocated, thereby allowing encoding efficiency to be improved compared to a case where a fixed length code is allocated to the entire quantization value.
In addition, it is also possible to improve the encoding efficiency by multidimensionalizing the quantization value. For example, when the digital data is quantized to 3 values of −1, 0, and +1, the number of bits taken to perform fixed length encoding with respect to the quantization value is 2 bits. Accordingly, when 4 quantization values are encoded individually, the number of bits taken to perform the encoding is 8 (=2×4) bits. In this regard, when 4 quantization values are multidimensionalized and encoded as a whole, the number of patterns of the quantization value in encoding unit is 81 (=34), and the number of bits taken to perform the encoding is 7 bits.
Further, it is understood that more efficient encoding is able to be realized by combining the Huffman encoding and the multidimensional encoding. However, the code book becomes bigger as the number of dimensions of the multidimensional encoding increases.
In addition, in the encoding with the combination of the Huffman encoding and the multidimensional encoding, a method by which the encoding efficiency is further improved is also devised by studying the encoding in a case where the entire quantization values in encoding unit are 0 (for example, refer to PTL 1).